//
//  mb_hash.c
//  MBAudio
//
//  Created by avansc on 4/18/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

/* The MIT License
 
 Copyright (c) 2008, by Attractive Chaos <attractivechaos@aol.co.uk>
 
 Permission is hereby granted, free of charge, to any person obtaining
 a copy of this software and associated documentation files (the
 "Software"), to deal in the Software without restriction, including
 without limitation the rights to use, copy, modify, merge, publish,
 distribute, sublicense, and/or sell copies of the Software, and to
 permit persons to whom the Software is furnished to do so, subject to
 the following conditions:
 
 The above copyright notice and this permission notice shall be
 included in all copies or substantial portions of the Software.
 
 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
 BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 SOFTWARE.
 */


#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include "MBAudio.h"

#ifdef __cplusplus
extern "C" {
#endif

static const uint32_t __ac_prime_list[32] = {
    0ul, 3ul, 11ul, 23ul, 53ul,
    97ul, 193ul, 389ul, 769ul, 1543ul,
    3079ul, 6151ul, 12289ul, 24593ul, 49157ul,
    98317ul, 196613ul, 393241ul, 786433ul, 1572869ul,
    3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul,
    100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul,
    3221225473ul, 4294967291ul
};

static const double __ac_HASH_UPPER = 0.77;

    uint32_t __ac_X31_hash_string(const char *s);
    mb_pUIMap_t *mb_init_pUIMap(void);
    void mb_destroy_pUIMap(mb_pUIMap_t *h);
    void mb_clear_pUIMap(mb_pUIMap_t *h);
    uint32_t mb_get_pUIMap(mb_pUIMap_t *h, const char *key);
    void mb_resize_pUIMap(mb_pUIMap_t *h, uint32_t new_n_buckets);
    uint32_t mb_put_pUIMap(mb_pUIMap_t *h, const char *key, int *ret);
    void mb_del_pUIMap(mb_pUIMap_t *h, uint32_t x);
    
uint32_t __ac_X31_hash_string(const char *s)
{
    uint32_t h = *s;
    if (h)
        for (++s; *s; ++s)
            h = (h << 5) - h + *s;
    return h;
}

mb_pUIMap_t *mb_init_pUIMap()
{
    return (mb_pUIMap_t *) calloc(1, sizeof(mb_pUIMap_t));
}

void mb_destroy_pUIMap(mb_pUIMap_t *h)
{
    if (h) {
        free(h->keys);
        free(h->flags);
        free(h->vals);
        free(h);
    }
}

void mb_clear_pUIMap(mb_pUIMap_t *h)
{
    if (h && h->flags) {
        memset(h->flags, 0xaa,
               ((h->n_buckets >> 4) + 1) * sizeof(uint32_t));
        h->size = h->n_occupied = 0;
    }
}

uint32_t mb_get_pUIMap(mb_pUIMap_t *h, const char *key)
{
    if (h->n_buckets) {
        uint32_t inc, k, i, last;
        k = __ac_X31_hash_string(key);
        i = k % h->n_buckets;
        inc = 1 + k % (h->n_buckets - 1);
        last = i;
        while (!((h->flags[i >> 4] >> ((i & 0xfU) << 1)) & 2)
               && (((h->flags[i >> 4] >> ((i & 0xfU) << 1)) & 1)
                   || !(strcmp(h->keys[i], key) == 0))) {
                   if (i + inc >= h->n_buckets)
                       i = i + inc - h->n_buckets;
                   else
                       i += inc;
                   if (i == last)
                       return h->n_buckets;
               }
        return ((h->flags[i >> 4] >> ((i & 0xfU) << 1)) & 3) ? h->
	    n_buckets : i;
    } else
        return 0;
}

void mb_resize_pUIMap(mb_pUIMap_t *h, uint32_t new_n_buckets)
{
    uint32_t *new_flags = 0;
    uint32_t j = 1; {
        uint32_t t = 32 - 1;
        while (__ac_prime_list[t] > new_n_buckets)
            --t;
        new_n_buckets = __ac_prime_list[t + 1];
        if (h->size >= (uint32_t) (new_n_buckets * __ac_HASH_UPPER + 0.5))
            j = 0;
        else {
            new_flags =
            (uint32_t *) malloc(((new_n_buckets >> 4) + 1) *
                                sizeof(uint32_t));
            memset(new_flags, 0xaa,
                   ((new_n_buckets >> 4) + 1) * sizeof(uint32_t));
            if (h->n_buckets < new_n_buckets) {
                h->keys =
                (const char * *) realloc(h->keys,
                                         new_n_buckets *
                                         sizeof(const char *));
                if (1)
                    h->vals =
                    (unsigned int **) realloc(h->vals,
                                              new_n_buckets *
                                              sizeof(unsigned int *));
            }
        }} if (j) {
            for (j = 0; j != h->n_buckets; ++j) {
                if (((h->flags[j >> 4] >> ((j & 0xfU) << 1)) & 3) == 0) {
                    const char * key = h->keys[j];
                    unsigned int *val;
                    if (1)
                        val = h->vals[j];
                    (h->flags[j >> 4] |= 1ul << ((j & 0xfU) << 1));
                    while (1) {
                        uint32_t inc, k, i;
                        k = __ac_X31_hash_string(key);
                        i = k % new_n_buckets;
                        inc = 1 + k % (new_n_buckets - 1);
                        while (!((new_flags[i >> 4] >> ((i & 0xfU) << 1)) & 2)) {
                            if (i + inc >= new_n_buckets)
                                i = i + inc - new_n_buckets;
                            else
                                i += inc;
                        }
                        (new_flags[i >> 4] &= ~(2ul << ((i & 0xfU) << 1)));
                        if (i < h->n_buckets
                            && ((h->flags[i >> 4] >> ((i & 0xfU) << 1)) & 3) ==
                            0) { {
                            const char * tmp = h->keys[i];
                            h->keys[i] = key;
                            key = tmp;
                        }
                            if (1) {
                                unsigned int *tmp = h->vals[i];
                                h->vals[i] = val;
                                val = tmp;
                            }
                            (h->flags[i >> 4] |= 1ul << ((i & 0xfU) << 1));
                        } else {
                            h->keys[i] = key;
                            if (1)
                                h->vals[i] = val;
                            break;
                        }
                    }
                }
            }
            if (h->n_buckets > new_n_buckets) {
                h->keys =
                (const char * *) realloc(h->keys,
                                         new_n_buckets * sizeof(const char *));
                if (1)
                    h->vals =
                    (unsigned int **) realloc(h->vals,
                                              new_n_buckets *
                                              sizeof(unsigned int *));
            }
            free(h->flags);
            h->flags = new_flags;
            h->n_buckets = new_n_buckets;
            h->n_occupied = h->size;
            h->upper_bound = (uint32_t) (h->n_buckets * __ac_HASH_UPPER + 0.5);
        }
}

uint32_t mb_put_pUIMap(mb_pUIMap_t *h, const char *key, int *ret)
{
    uint32_t x;
    if (h->n_occupied >= h->upper_bound) {
        if (h->n_buckets > (h->size << 1))
            mb_resize_pUIMap(h, h->n_buckets - 1);
        else
            mb_resize_pUIMap(h, h->n_buckets + 1);
    }
    {
        uint32_t inc, k, i, site, last;
        x = site = h->n_buckets;
        k = __ac_X31_hash_string(key);
        i = k % h->n_buckets;
        if (((h->flags[i >> 4] >> ((i & 0xfU) << 1)) & 2))
            x = i;
        else {
            inc = 1 + k % (h->n_buckets - 1);
            last = i;
            while (!((h->flags[i >> 4] >> ((i & 0xfU) << 1)) & 2)
                   && (((h->flags[i >> 4] >> ((i & 0xfU) << 1)) & 1)
                       || !(strcmp(h->keys[i], key) == 0))) {
                       if (((h->flags[i >> 4] >> ((i & 0xfU) << 1)) & 1))
                           site = i;
                       if (i + inc >= h->n_buckets)
                           i = i + inc - h->n_buckets;
                       else
                           i += inc;
                       if (i == last) {
                           x = site;
                           break;
                       }
                   }
            if (x == h->n_buckets) {
                if (((h->flags[i >> 4] >> ((i & 0xfU) << 1)) & 2)
                    && site != h->n_buckets)
                    x = site;
                else
                    x = i;
            }
        }
    }
    if (((h->flags[x >> 4] >> ((x & 0xfU) << 1)) & 2)) {
        h->keys[x] = key;
        (h->flags[x >> 4] &= ~(3ul << ((x & 0xfU) << 1)));
        ++h->size;
        ++h->n_occupied;
        *ret = 1;
    } else if (((h->flags[x >> 4] >> ((x & 0xfU) << 1)) & 1)) {
        h->keys[x] = key;
        (h->flags[x >> 4] &= ~(3ul << ((x & 0xfU) << 1)));
        ++h->size;
        *ret = 2;
    } else
        *ret = 0;
    return x;
}

void mb_del_pUIMap(mb_pUIMap_t *h, uint32_t x)
{
    if (x != h->n_buckets
        && !((h->flags[x >> 4] >> ((x & 0xfU) << 1)) & 3)) {
        (h->flags[x >> 4] |= 1ul << ((x & 0xfU) << 1));
        --h->size;
    }
}
    
#ifdef __cplusplus
}
#endif
